package leetcode71_80;

/**
 * @author shhjiang_001
 * @create 2020-06-22 10:34
 */

        /*
        编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
        每行中的整数从左到右按升序排列。
        每行的第一个整数大于前一行的最后一个整数。

        示例 1:

        输入:
        matrix = [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
        ]
        target = 3
        输出: true
        */

public class Solution74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;
        if (target < matrix[0][0] || target > matrix[m-1][n-1]) return false;
        int leRow = 0;
        int riRow = m-1;
        while (true){
            if (leRow == riRow) break;
            int temp = (leRow+riRow)/2;
            if (matrix[temp][n-1] >= target){
                riRow=temp;
            } else {
                leRow=temp+1;
            }
        }
        int leLine = 0;
        int riLine = n-1;
        while (true){
            if (leLine == riLine){
                if (matrix[leRow][leLine] == target) return true;
                break;
            }
            int temp = (leLine+riLine)/2;
            if (matrix[leRow][temp] == target ) return true;
            if (matrix[leRow][temp] > target){
                riLine = temp-1;
            }else {
                leLine = temp+1;
            }

        }
        return false;
    }
}
